package leetcode.动态规划.完全背包;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Leetcode139 {
    //dfs+记忆化搜索
    public boolean wordBreak(String s, List<String> wordDict) {
        Boolean[] memo = new Boolean[s.length()];
        Set<String> list = new HashSet<String>(wordDict);
        return dfs(s,list,0,memo);
    }

    public boolean dfs(String s, Set<String> wordDict,int index,Boolean[] memo){
        if(index == s.length()){
            return true;
        }
        if(memo[index]!=null){
            return memo[index];
        }
        for(int i = index;i<s.length();i++){
            if(wordDict.contains(s.substring(index,i+1))&&dfs(s,wordDict,i+1,memo)){
                return memo[index] = true;
            }
        }
        return memo[index] = false;
    }
    //动态规划
    public boolean wordBreak1(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        Set<String> set = new HashSet<>(wordDict);
        for(int i = 1;i<=s.length();i++){
            for(int j = 0;j<i;j++){
                String word = s.substring(j,i);
                if(dp[j]&&set.contains(word)){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
